/************************************************************************
 * Strathclyde Planning Group, Department of Computer and Information Sciences,
 * University of Strathclyde, Glasgow, UK http://planning.cis.strath.ac.uk/
 * 
 * Copyright 2007, Keith Halsey Copyright 2008, Andrew Coles and Amanda Smith
 * 
 * (Questions/bug reports now to be sent to Andrew Coles)
 * 
 * This file is part of JavaFF.
 * 
 * JavaFF is free software: you can redistribute it and/or modify it under the
 * terms of the GNU General Public License as published by the Free Software
 * Foundation, either version 2 of the License, or (at your option) any later
 * version.
 * 
 * JavaFF is distributed in the hope that it will be useful, but WITHOUT ANY
 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
 * A PARTICULAR PURPOSE. See the GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License along with
 * JavaFF. If not, see <http://www.gnu.org/licenses/>.
 * 
 ************************************************************************/

/**
 * refactoring made by Ronen Pinko 2009_12_30
 */

package javaff.search;

import java.util.Comparator;
import java.util.HashSet;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;

import javaff.planning.FFState;
import javaff.planning.Filter;

public class BestFirstSearch extends Search {

	private final Set<FFState>			visited		= new HashSet<FFState>();
	private final SortedSet<FFState>	hValueSortedStates;
	private final Filter				filter;
	private int							nodeCount	= 0;

	public BestFirstSearch(FFState start, Filter f,
			Comparator<FFState> comparator) {
		super(start);
		this.hValueSortedStates = new TreeSet<FFState>(comparator);
		this.filter = f;
	}

	private void updateOpen(FFState state) {
		hValueSortedStates
				.addAll(state.getNextStates(filter.getActions(state)));
	}

	private FFState removeNext() {
		final FFState next = next();
		hValueSortedStates.remove(next);
		return next;
	}

	private FFState next() {
		return hValueSortedStates.first();
	}

	public boolean needToVisit(FFState s) {
		return visited.add(s);
	}

	@Override
	public FFState search() {
		hValueSortedStates.add(start);
		while (!hValueSortedStates.isEmpty()) {
			FFState s = removeNext();
			if (needToVisit(s)) {
				nodeCount++;
				if (s.goalReached()) {
					return s;
				} else {
					updateOpen(s);
				}
			}

		}
		return null;
	}

	public int getNodeCount() {
		return nodeCount;
	}

}
